Fast Conditional Density Estimation for Quantitative Structure%2DActivity Relationships.
Many methods for quantitative structure-activity relationships (QSARs) deliver point estimates only, without quantifying the uncertainty inherent in the prediction. One way to quantify the uncertainy of a QSAR prediction is to predict the conditional density of the activity given the structure instead of a point estimate. If a conditional density estimate is available, it is easy to derive prediction intervals of activities. In this paper, we experimentally evaluate and compare three methods for conditional density estimation for their suitability in QSAR modeling. In contrast to traditional methods for conditional density estimation, they are based on generic machine learning schemes, more specifically, class probability estimators. Our experiments show that a kernel estimator based on class probability estimates from a random forest classifier is highly competitive with Gaussian process regression, while taking only a fraction of the time for training. Therefore, generic machine-learning based methods for conditional density estimation may be a good and fast option for quantifying uncertainty in QSAR modeling.
Integer Linear Programming Models for Constrained Clustering.

Equation Discovery for Model Identification in Respiratory Mechanics of the Mechanically Ventilated Human Lung.

Mining Class%2DCorrelated Patterns for Sequence Labeling.

Adapted Transfer of Distance Measures for Quantitative Structure%2DActivity Relationships.

Latent Structure Pattern Mining.

Online Structural Graph Clustering Using Frequent Subgraph Mining.

Pitfalls of supervised feature selection.

Predicting biodegradation products and pathways a hybrid knowledge%2D and machine learning%2Dbased approach.

A Study of Hierarchical and Flat Classification of Proteins.
Abstract — Automatic classification of proteins using machine learning is an important problem that has received significant attention in the literature. One feature of this problem is that expert-defined hierarchies of protein classes exist and can potentially be exploited to improve classification performance. In this article we investigate empirically whether this is the case for two such hierarchies. We compare multi-class classification techniques that exploit the information in those class hierarchies and those that do not, using logistic regression, decision trees, bagged decision trees, and support vector machines as the underlying base learners. In particular, we compare hierarchical and flat variants of ensembles of nested dichotomies. The latter have been shown to deliver strong classification performance in multi-class settings. We present experimental results for synthetic, fold recognition, enzyme classification, and remote homology detection data. Our results show that exploiting the class hierarchy improves performance on the synthetic data, but not in the case of the protein classification problems. Based on this we recommend that strong flat multi-class methods be used as a baseline to establish the benefit of exploiting class hierarchies in this area. Index Terms — protein classification, hierarchical classification, multi-class classification I.
Interpreting PET scans by structured patient data a data mining case study in dementia research.

Prediction of Mechanical Lung Parameters Using Gaussian Process Models.

Data%2DEfficient Information%2DTheoretic Test Selection.

Subgroup Discovery for Test Selection A Novel Approach and Its Application to Breast Cancer Diagnosis.

Finding Relational Associations in HIV Resistance Mutation Data.

Large%2Dscale graph mining using backbone refinement classes.

Enhancing navigation in biomedical databases by community voting and database%2Ddriven text classification.

Kernel%2DBased Inductive Transfer.
Abstract. Methods for inductive transfer take advantage of knowledge from previous learning tasks to solve a newly given task. In the context of supervised learning, the task is to find a suitable bias for a new dataset, given a set of known datasets. In this paper, we take a kernelbased approach to inductive transfer, that is, we aim at finding a suitable kernel for the new data. In our setup, the kernel is taken from the linear span of a set of predefined kernels. To find such a kernel, we apply convex optimization on two levels. On the base level, we propose an iterative procedure to generate kernels that generalize well on the known datasets. On the meta level, we combine those kernels in a minimization criterion to predict a suitable kernel for the new data. The criterion is based on a meta kernel capturing the similarity of two datasets. In experiments on small molecule and text data, kernel-based inductive transfer showed a statistically significant improvement over the best individual kernel in almost all cases.
SINDBAD and SiQL An Inductive Database and Query Language in the Relational Model.

An inductive database and query language in the relational model.

Interpreting PET Scans by Structured Patient Data A Data Mining Case Study in Dementia Research.

Data%2Ddriven extraction of relative reasoning rules to limit combinatorial explosion in biodegradation pathway prediction.

Margin%2Dbased first%2Dorder rule learning.
Learning sets of first-order rules has a long tradition in machine learning and inductive logic programming. While most traditional systems follow a separateand-conquer approach, many modern systems are based on statistical considerations, such as ensemble theory, large margin classification or graphical models. In
Inductive logic programming for gene regulation prediction.
One of the central goals in computational and systems biology is to understand the mechanisms of gene transcriptional regulation on a system-wide level. The efforts are often based on high-throughput genomic data of model organisms such as S. cerevisiae. The goal of this work is to learn a model of gene regulation
Optimizing Feature Sets for Structured Data.
Abstract. Choosing a suitable feature representation for structured data is a non-trivial task due to the vast number of potential candidates. Ideally, one would like to pick a small, but informative set of structural features, each providing complementary information about the instances. We frame the search for a suitable feature set as a combinatorial optimization problem. For this purpose, we define a scoring function that favors features that are as dissimilar as possible to all other features. The score is used in a stochastic local search (SLS) procedure to maximize the diversity of a feature set. In experiments on small molecule data, we investigate the effectiveness of a forward selection approach with two different linear classification schemes. 1
Leveraging Chemical Background Knowledge for the Prediction of Growth Inhibition.

A statistical approach to rule learning.
We present a new, statistical approach to rule learning. Doing so, we address two of the problems inherent in traditional rule learning: The computational hardness of finding rule sets with low training error and the need for capacity control to avoid overfitting. The chosen representation involves weights attached to rules. Instead of optimizing the error rate directly, we optimize for rule sets that have large margin and low variance. This can be formulated as a convex optimization problem allowing for efficient computation. Given the representation and the optimization procedure, we effectively yield weighted clauses in a CNFlike representation. To avoid overfitting, we propose a model selection strategy that utilizes a novel concentration inequality. Empirical tests show that the system is competitive with existing rule learning algorithms and that its flexible learning bias can be adjusted to improve predictive accuracy considerably. 1.
Inductive Logic Programming for Gene Regulation Prediction.
One of the central goals in computational and systems biology is to understand the mechanisms of gene transcriptional regulation on a system-wide level. The efforts are often based on high-throughput genomic data of model organisms such as S. cerevisiae. The goal of this work is to learn a model of gene regulation
Margin%2DBased First%2DOrder Rule Learning.
Learning sets of first-order rules has a long tradition in machine learning and inductive logic programming. While most traditional systems follow a separateand-conquer approach, many modern systems are based on statistical considerations, such as ensemble theory, large margin classification or graphical models. In
Optimal String Mining Under Frequency Constraints.
Abstract. We propose a new algorithmic framework that solves frequency-related data mining queries on databases of strings in optimal time, i.e., in time linear in the input and the output size. The additional space is linear in the input size. Our framework can be used to mine frequent strings, emerging strings and strings that pass other statistical tests, e.g., the χ 2-test. In contrast to the presented result for strings, no optimal algorithms are known for other pattern domains such as itemsets. The key to our approach are several recent results on index structures for strings, among them suffix- and lcp-arrays, and a new preprocessing scheme for range minimum queries. The advantages of array-based data structures (compared with dynamic data structures such as trees) are good locality behavior and extensibility to secondary memory. We test our algorithm on real-world data from computational biology and demonstrate that the approach also works well in practice. 1
Learning a Predictive Model for Growth Inhibition from the NCI DTP Human Tumor Cell Line Screening Data Does Gene Expression Make a Difference%3F%
We address the problem of learning a predictive model for growth inhibition from the NCI DTP human tumor cell line screening data. Extending the classical Quantitative Structure Activity Relationship paradigm, we investigate whether including gene expression data leads to a statistically significant improvement of prediction quality. Our analysis shows that the straightforward approach of including individual gene expression as features does not necessarily improve, but on the contrary, may degrade performance significantly. When gene expression information is aggregated, for instance by features representing the correlation with reference cell lines, performance can be improved significantly. Further improvements may be expected if the learning task is structured by grouping features and instances. 1.
Learning a Predictive Model for Growth Inhibition from the NCI DTP Human Tumor Cell Line Screening Data Does Gene Expression Make a Difference%3F%
We address the problem of learning a predictive model for growth inhibition from the NCI DTP human tumor cell line screening data. Extending the classical Quantitative Structure Activity Relationship paradigm, we investigate whether including gene expression data leads to a statistically significant improvement of prediction quality. Our analysis shows that the straightforward approach of including individual gene expression as features does not necessarily improve, but on the contrary, may degrade performance significantly. When gene expression information is aggregated, for instance by features representing the correlation with reference cell lines, performance can be improved significantly. Further improvements may be expected if the learning task is structured by grouping features and instances. 1.
A new representation for protein secondary structure prediction based on frequent patterns.

Introduction to the special issue on multi%2Drelational data mining and statistical relational learning.

Inductive Logic Programming
 
Analyzing microarray data using quantitative association rules.

Fast Frequent String Mining Using Suffix Arrays.
 
Extending Function Point Analysis of Object%2DOriented Requirements Specifications.

Inductive Databases in the Relational Model The Data as the Bridge.
Abstract. We present a new and comprehensive approach to inductive databases in the relational model. The main contribution is a new inductive query language extending SQL, with the goal of supporting the whole knowledge discovery process, from pre-processing via data mining to post-processing. A prototype system supporting the query language was developed in the SINDBAD (structured inductive database development) project. Setting aside models and focusing on distance-based and instance-based methods, closure can easily be achieved. An example scenario from the area of gene expression data analysis demonstrates the power and simplicity of the concept. We hope that this preliminary work will help to bring the fundamental issues, such as the integration of various pattern domains and data mining techniques, to the attention of the inductive database community. 1
Ensembles of Balanced Nested Dichotomies for Multi%2Dclass Problems.
Abstract. A system of nested dichotomies is a hierarchical decomposition of a multi-class problem with c classes into c − 1two-classproblems and can be represented as a tree structure. Ensembles of randomlygenerated nested dichotomies have proven to be an effective approach to multi-class learning problems [1]. However, sampling trees by giving each tree equal probability means that the depth of a tree is limited only by the number of classes, and very unbalanced trees can negatively affect runtime. In this paper we investigate two approaches to building balanced nested dichotomies—class-balanced nested dichotomies and data-balanced nested dichotomies—and evaluate them in the same ensemble setting. Using C4.5 decision trees as the base models, we show that both approaches can reduce runtime with little or no effect on accuracy, especially on problems with many classes. We also investigate the effect of caching models when building ensembles of nested dichotomies. 1
Quantitative Association Rules Based on Half%2DSpaces An Optimization Approach.

Ensembles of nested dichotomies for multi%2Dclass problems.
Nested dichotomies are a standard statistical technique for tackling certain polytomous classification problems with logistic regression. They can be represented as binary trees that recursively split a multi-class classification task into a system of dichotomies and provide a statistically sound way of applying two-class learning algorithms to multi-class problems (assuming these algorithms generate class probability estimates). However, there are usually many candidate trees for a given problem and in the standard approach the choice of a particular tree is based on domain knowledge that may not be available in practice. An alternative is to treat every system of nested dichotomies as equally likely and to form an ensemble classifier based on this assumption. We show that this approach produces more accurate classifications than applying C4.5 and logistic regression directly to multi-class problems. Our results also show that ensembles of nested dichotomies produce more accurate classifiers than pairwise classification if both techniques are used with C4.5, and comparable results for logistic regression. Compared to error-correcting output codes, they are preferable if logistic regression is used, and comparable in the case of C4.5. An additional benefit is that they generate class probability estimates. Consequently they appear to be a good generalpurpose method for applying binary classifiers to multi-class problems.
Towards tight bounds for rule learning.
While there is a lot of empirical evidence showing that traditional rule learning approaches work well in practice, it is nearly impossible to derive analytical results about their predictive accuracy. In this paper, we investigate rule-learning from a theoretical perspective. We show that the application of McAllester’s PAC-Bayesian bound to rule learning yields a practical learning algorithm, which is based on ensembles of weighted rule sets. Experiments with the resulting learning algorithm show not only that it is competitive with state-of-the-art rule learners, but also that its error rate can often be bounded tightly. In fact, the bound turns out to be tighter than one of the “best ” bounds for a practical learning scheme known so far (the Set Covering Machine). Finally, we prove that the bound can be further improved by allowing the learner to abstain from uncertain predictions. 1.
Frequent free tree discovery in graph data.
In recent years, researchers in graph mining have been exploring linear paths as well as subgraphs as pattern languages. In this paper, we are investigating the middle ground between these two extremes: mining free (that is, unrooted) trees in graph data. The motivation for this is the need to upgrade linear path patterns, while avoiding complexity issues with subgraph patterns. Starting from such complexity considerations, we are defining free trees and their canonical form, before we present FreeTreeMiner, an algorithm making efficient use of this canonical form during search. Experiments with two datasets from the National Cancer Institute’s Developmental Therapeutics Program (DTP), anti-HIV and anti-cancer screening data, are reported. 1
Coupling and cohesion metrics for knowledge%2Dbased systems using frames and rules.

Experiments In Predicting Biodegradability.
. We present a novel application of inductive logic programming  (ILP) in the area of quantitative structure-activity relationships  (QSARs). The activity we want to predict is the biodegradability of  chemical compounds in water. In particular, the target variable is the  half-life in water for aerobic aqueous biodegradation. Structural descriptions  of chemicals in terms of atoms and bonds are derived from the  chemicals&#039; SMILES encodings. Definition of substructures are used as  background knowledge. Predicting biodegradability is essentially a regression  problem, but we also consider a discretized version of the target  variable. We thus employ a number of relational classification and regression  methods on the relational representation and compare these to  propositional methods applied to different propositionalisations of the  problem. Some expert comments on the induced theories are also given.  1 Introduction  The persistence of chemicals in the environment (or to environmen...
Data Mining and Machine Learning Techniques for the Identification of Mutagenicity Inducing Substructures and Structure Activity Relationships of Noncongeneric Compounds.

Metamodel%2DCompliance Checking of Requirements in a Semiformal Representation.
Checking requirements is highly desirable but hard to achieve in practice,  where only word processors are used in most projects. While in this case  reviews are more or less the only means, formal representations allow for a variety  of automated checks. Unfortunately, formal representations of requirements  are rarely available in real-world projects. Semiformal representations are easier  to obtain and still offer some possibilities for automated checks. Based on an  object-oriented hypertext representation, we present an implemented approach  for compliance checks against a metamodel.
Stochastic Local Search in k%2DTerm DNF Learning.
A novel native stochastic local search algorithm for solving k-term DNF problems is presented. It is evaluated on hard k-term DNF problems that lie on the phase transition and compared to the performance of GSAT and WalkSAT type algorithms on SAT encodings of k-term DNF problems. We also evaluate state-of-the-art separate and conquer algorithms on these problems. Finally, we demonstrate the practical relevance of our algorithm on a chess endgame database.
Generalized Version Space Trees.
We introduce generalized version space trees, a novel data structure that serves as a condensed representation in inductive databases for graph mining. Generalized version space trees allow for a comfortable representation of version spaces and a natural way to efficiently process inductive queries and operations on version spaces. In particular, we focus on using generalized version space trees in the field of mining free (i.e. unrooted) trees in graph databases. Experiments with two data sets from the National Cancer Institute&#039;s Developmental Therapeutics Program (DTP) indicate that generalized version space trees can boost inductive queries considerably while featuring moderately increased space requirements in comparison to a version space representation based on boundary sets.
Towards Discovering Structural Signatures of Protein Folds Based on Logical Hidden Markov Models.
Kristian Kersting    Tapani Raiko    Stefan Kramer    Luc De Raedt    Machine Learning Lab, Computer Science Department,  University of Freiburg  Georges-Koehler-Alle 079, 79112 Freiburg, Germany    Laboratory of Computer and Information Science,  Helsinki University of Technology  P.O. Box 540, Helsinki, FIN-02015 HUT, Finland  Keywords: Hidden Markov Models, Probabilistic Modeling, First-Order Logic, Structural Signatures, SCOP  With the growing number of determined protein structures and the availability of classification schemes, it becomes increasingly important to develop computer methods that automatically extract structural signatures for classes of proteins. We present a new Machine Learning technique, Logical Hidden Markov Models (LOHMMs), and apply it to the task of finding structural signatures of folds according to the classification scheme SCOP.
A Survey of the Predictive Toxicology Challenge 2000%2D2001.

Statistical Evaluation of the Predictive Toxicology Challenge 2000%2D2001.
Motivation: The development of in silico models to predict chemical carcinogenesis from molecular structure would help greatly to prevent environmentally caused cancers. The Predictive Toxicology Challenge (PTC) competition wasorganized to test the state-of-the-art in applying machine learning to form such predictive models.
Phase Transitions and Stochastic Local Search in k%2DTerm DNF Learning.
In the past decade, there has been a lot of interest in phase transitions  within artificial intelligence, and more recently, in machine learning and inductive  logic programming. We investigate phase transitions in learning k-term DNF  boolean formulae, a practically relevant class of concepts. We do not only show  that there exist phase transitions, but also characterize and locate these phase  transitions using the parameters k, the number of positive and negative examples,  and the number of boolean variables. Subsequently, we investigate stochastic local  search (SLS) for k-term DNF learning. We compare several variants that first  reduce k-term DNF to SAT and then apply well-known SLS algorithms, such as  GSAT and WalkSAT. Our experiments indicate that WalkSAT is able to solve the  largest fraction of hard problem instances.
Transformation%2DBased Regression.
In this paper, we introduce Transformation-Based Regression (TBR), a novel rule-based, symbolic regression technique based on Transformation-Based Learning (TBL). Although Transformation-Based Learning has been introduced already a couple of years ago, it has not yet been considered for regression-type tasks. The proposed method should be particularly useful for learning from examples with a given neighborhood relation, where the dependent variable of one example also depends on neighboring examples. Thus, the method should have a potential for learning from sequence and spatial data. In the paper, we demonstrate the capabilities and limitations of the approach in two highly complex real-world domains, musicology and speech synthesis.
Analysis of respiratory pressure%2Dvolume curves in intensive care medicine using inductive machine learning.
We present a case study of Machine Learning and Data Mining in intensive care  medicine. In the study, we compared different methods of measuring pressure-volume curves in  artificially ventilated patients suffering from the Adult Respiratory Distress Syndrome (ARDS).
The Levelwise Version Space Algorithm and its Application to Molecular Fragment Finding.
A tight integration of Mitchell&#039;s version space algorithm with Agrawal et al.&#039;s Apriori algorithm is presented. The algorithm can be used to generate patterns that satisfy a variety of constraints on data. Constraints that can be impoesed on...
Feature Construction with Version Spaces for Biochemical Applications.

The Levelwise Version Space Algorithm and its Application to Molecular Fragment Finding.
A tight integration of Mitchell&#039;s version space algorithm with Agrawal et al.&#039;s Apriori algorithm is presented. The algorithm can be used to generate patterns that satisfy a variety of constraints on data. Constraints that can be impoesed on...
Demand%2DDriven Construction of Structural Features in ILP.
This paper tackles the problem that methods for propositionalization and feature construction in first-order logic to date construct features in a rather unspecific way. That is, they do not construct features &#034;on demand&#034;, but rather in advance and without detecting the need for a representation change. Even if structural features are required, current methods do not construct these features in a goal-directed fashion. In previous work, we presented...
Molecular feature mining in HIV data.

The Predictive Toxicology Challenge 2000%2D2001.
Motivation: The development of in silico models to predict chemical carcinogenesis from molecular structure would help greatly to prevent environmentally caused cancers. The Predictive Toxicology Challenge (PTC) competition wasorganized to test the state-of-the-art in applying machine learning to form such predictive models.
Prediction of Ordinal Classes Using Regression Trees.
This paper is devoted to the problem of learning to predict ordinal (i.e., ordered discrete) classes using classification and regression trees. We start with S-CART, a tree induction algorithm, and study various ways of transforming it into a learner for ordinal classification tasks. These algorithm variants are compared on a number of benchmark data sets to verify the relative strengths and weaknesses of the strategies and to study the trade-off between optimal categorical classification accuracy (hit rate) and minimum distance-based error. Preliminary results indicate that this is a promising avenue towards algorithms that combine aspects of classification and regression.
Learning to Use Operational Advice.
 We address the problem of advice-taking in a given domain, in particular for building a game-playing program. Our approach to solving it strives for the application of machine learning techniques throughout, i.e., for avoiding knowledge elicitation by any other means as much as possible. In particular, we build upon existing work on the operationalization of advice by machine and assume that advice is already available in operational form. The relative importance of this advice is, however, not yet known and can therefore not be utilized well by a program. This paper presents an approach to determine the relative importance for a given situation through reinforcement learning. We implemented this approach for the game of Hearts and gathered some empirical evidence on its usefulness through experiments. The results show that the programs built according to our approach learned to make good use of the given operational advice.   
Learning to Use Operational Advice.
 We address the problem of advice-taking in a given domain, in particular for building a game-playing program. Our approach to solving it strives for the application of machine learning techniques throughout, i.e., for avoiding knowledge elicitation by any other means as much as possible. In particular, we build upon existing work on the operationalization of advice by machine and assume that advice is already available in operational form. The relative importance of this advice is, however, not yet known and can therefore not be utilized well by a program. This paper presents an approach to determine the relative importance for a given situation through reinforcement learning. We implemented this approach for the game of Hearts and gathered some empirical evidence on its usefulness through experiments. The results show that the programs built according to our approach learned to make good use of the given operational advice.   
Bottom%2DUp Propositionalization.
. In this paper, we present a new method for propositionalization  that works in a bottom-up, data-driven manner. It is tailored for biochemical  databases, where the examples are 2-D descriptions of chemical  compounds. The method generates all frequent fragments (i.e., linearly  connected atoms) up to a user-specied length. A preliminary experiment  in the domain of carcinogenicity prediction showed that bottomup  propositionalization is a promising approach to feature construction  from relational data.  1 Introduction  One approach to handle relational learning problems is to transform them into propositional problems and subsequently apply propositional learning algorithms. This transformation requires the construction of features that capture relational properties of the learning examples. In this way, feature construction and model construction are decoupled. Such a transformation of a relational learning problem into a propositional one is called propositionalization. In this ...
Prediction of Ordinal Classes Using Regression Trees.
This paper is devoted to the problem of learning to predict ordinal (i.e., ordered discrete) classes using classification and regression trees. We start with S-CART, a tree induction algorithm, and study various ways of transforming it into a learner for ordinal classification tasks. These algorithm variants are compared on a number of benchmark data sets to verify the relative strengths and weaknesses of the strategies and to study the trade-off between optimal categorical classification accuracy (hit rate) and minimum distance-based error. Preliminary results indicate that this is a promising avenue towards algorithms that combine aspects of classification and regression.
Thesis Relational learning vs. propositionalization.

Semiautomatic Generation of Glossary Links A Practical Solution.
This paper applies the linguistic theory of relevance to the study of the way links work, insisting on the lyrical quality of the link-interpreting activity. It is argued that such a pragmatic approach can help us understand hypertext readers behavior, and thus be useful for authors and toolbuilders alike.
Experiments in Predicting Biodegradability.
. We present a novel application of inductive logic programming  (ILP) in the area of quantitative structure-activity relationships  (QSARs). The activity we want to predict is the biodegradability of  chemical compounds in water. In particular, the target variable is the  half-life in water for aerobic aqueous biodegradation. Structural descriptions  of chemicals in terms of atoms and bonds are derived from the  chemicals&#039; SMILES encodings. Definition of substructures are used as  background knowledge. Predicting biodegradability is essentially a regression  problem, but we also consider a discretized version of the target  variable. We thus employ a number of relational classification and regression  methods on the relational representation and compare these to  propositional methods applied to different propositionalisations of the  problem. Some expert comments on the induced theories are also given.  1 Introduction  The persistence of chemicals in the environment (or to environmen...
Combining Structure Search and Content Search for the World%2DWide Web.

A Case Study of Decomposing Functional Requirements Using Scenarios.

Stochastic Propositionalization of Non%2Ddeterminate Background Knowledge.
Both propositional and relational learning algorithms require a good representation to perform well in practice. Usually such a representation is either engineered manually by domain experts or derived automatically by means of so-called constructive induction. Inductive Logic Programming (ILP) algorithms put a somewhat less burden on the data engineering effort as they allow for a structured, relational representation of background knowledge. In chemical and engineering domains, a common representational device for graph-like structures are so-called non-determinate relations. Manually engineered features in such domains typically test for or count occurrences of specific substructures having specific properties. However, representations containing non-determinate relations pose a serious efficiency problem for most standard ILP algorithms. Therefore, we have devised a stochastic algorithm to automatically derive features from non-determinate background knowledge. The algorithm conduc...
Integrating Forward and Reverse Object%2DOriented Software Engineering.

Can We Benefit from Metrics in KBS Development%3F

Mining for Causes of Cancer Machine Learning Experiments at Various Levels of Detail.
This paper presents, from a methodological point of view, first results of an interdisciplinary project in scientific data mining. We analyze data about the carcinogenicity of chemicals derived from the carcinogenesis bioassay program, a long-term research study performed by the US National Institute of Environmental Health Sciences. The database contains detailed descriptions of 6823 tests performed with more than 330 compounds and animals of different species, strains and sexes. The chemical structures are described at the atom and bond level, and in terms of various relevant structural properties. The goal of this paper is to investigate the effects that various levels of detail and amounts of information have on the resulting hypotheses, both quantitatively and qualitatively. We apply relational and propositional machine learning algorithms to learning problems formulated as regression or as classification tasks. In addition, these experiments have been conducted with two learning ...
Structural Regression Trees.
In many real-world domains the task of machine learning algorithms is to learn a theory predicting numerical values. In particular several standard test domains used in Inductive Logic Programming (ILP) are concerned with predicting numerical values from examples and relational and mostly non-determinate background knowledge. However, so far no ILP algorithm except one can predict numbers and cope with non-determinate background knowledge. (The only exception is a covering algorithm called FORS.) In this paper we present Structural Regression Trees (SRT), a new algorithm which can be applied to the above class of problems by integrating the statistical method of regression trees into ILP. SRT constructs a tree containing a literal (an atomic formula or its negation) or a conjunction of literals in each node, and assigns a numerical value to each leaf. SRT provides more comprehensible results than purely statistical methods, and can be applied to a class of problems most other ILP syste...
Efficient Search for Strong Partial Determinations.
Our work offers both a solution to the problem of finding functional dependencies that are distorted by noise and to the open problem of efficiently finding strong (i.e., highly compressive) partial determinations per se. Briefly, we introduce a restricted form of search for partial determinations which is based on functional dependencies. Focusing attention on solely partial determinations derivable from overfitting functional dependencies enables efficient search for strong partial determinations. Furthermore, we generalize the compression-based measure for evaluating partial determinations to n-valued attributes. Applications to real-world data suggest that the restricted search indeed retrieves a subset of strong partial determinations in much shorter runtimes, thus showing the feasibility and usefulness of our approach. 1 Introduction  Functional dependencies [Mannila &amp; Raiha, 1994] are a fundamental form of knowledge to be discovered in databases. In real-world databases, however...
Compression%2DBased Evaluation of Partial Determinations.
Our work tackles the problem of finding partial determinations in databases and proposes a compression-based measure to evaluate them. Partial determinations can be viewed as generalizations of both functional dependencies and association rules, in that they are relational in nature and may have exceptions. Extending the measures used for evaluating association rules, namely support and confidence, to partial determinations leads to a few problems. We therefore propose a measure based on the minimum description length (MDL) principle to remedy this problem. We assume the hypothetical task of transmitting a given database  as efficiently as possible. The new measure estimates the compression achievable by transmitting partial determinations instead of the original data. It takes into account both the complexity and the correctness of a given partial determination, thus avoiding overfitting especially in the presence of noise. We also describe three different kinds of search using the ne...
